U.S. Pat. No. 5,832,262 describes the use of real-time hardware scheduling to assign tasks to different processors of a multi-processor system. The system comprises a scheduling processor and a plurality of processors that act as slaves to execute tasks scheduled by the scheduling processor. The scheduling processor identifies tasks to be executed and places them in a queue of executable tasks. Available slaves execute the tasks from the queue, under control of a real-time hardware scheduler.
U.S. Pat. No. 5,832,262 does not specify how the scheduling processor selects tasks to be placed in the queue, but it is known to use a task graph for this purpose. The task graph expresses relations between tasks, indicating for each task which predecessor tasks must have been completed before the task can be executed. Thus, a task can be placed in the queue for execution when it is has been detected that the predecessors specified in the task graph have completed execution. U.S. Pat. No. 5,832,262 uses pre-compiled scheduling based on priorities that define the relative urgencies of the tasks, but not on data dependency.
Conventionally, task graphs are prepared by the programmer or a compiler, by identifying variables used in a task and tracing to the tasks that produce these variables. For a large set of tasks a task graph can become quite extensive. Moreover, static task graphs are presumed. The tasks have to be formulated in such a way that dynamically variable dependency does not occur between tasks. Thus in image processing applications for example, it is excluded to realize static task graphs handling variable dependency as a result of variable motion vectors other than by expressing dependency in terms of dependence on images as a whole.